/**
 * 快速排序: 原理, 就是前后互相相对行走, 直到碰见. 
 *         时间复杂度为O(nlogn)
 *          空间复杂度为O(1)
 * 
 * 冒泡排序: 原理, 就是两遍循环, 直到相对位置固定. 
 *          时间复杂度为O(n**2)
 *          空间复杂度为O(1)
 */
    //  arr的数据类型为数字数组. 
    function quickSort(arr, from, to) {
        let i = from;
        let j = to;
        // 把第一个值作为基准值
        let key = arr[from]
        // 如果数组from >= to, 则表示排序的过程已经结束, 或者代3排序数组长度为0,1 
        if (i >= j) return arr

        // 如果需要进行排序的待排序数组
        while (i < j) {
            while (arr[i] <= key && i <= j) {
                i++
            }
            while (arr[j] > key && i < j) {
                j++
            }

            if (i < j) {
                let temp
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            }
        }
        arr[from] = arr[i]
        arr[i] = key
        quickSort(arr, from, i - 1)
        quickSort(arr, i + 1, to)
    }

var arr = [3, 3, -5, 6, 0, 2, -1, -1, 3];
console.log(arr);
quickSort(arr, 0, arr.length - 1);
console.log(arr);
